Search results for "Information complexity"
showing 4 items of 4 documents
Entropic descriptor of a complex behaviour
2009
We propose a new type of entropic descriptor that is able to quantify the statistical complexity (a measure of complex behaviour) by taking simultaneously into account the average departures of a system's entropy S from both its maximum possible value Smax and its minimum possible value Smin. When these two departures are similar to each other, the statistical complexity is maximal. We apply the new concept to the variability, over a range of length scales, of spatial or grey-level pattern arrangements in simple models. The pertinent results confirm the fact that a highly non-trivial, length-scale dependence of the entropic descriptor makes it an adequate complexity-measure, able to disting…
Quadratically Tight Relations for Randomized Query Complexity
2020
In this work we investigate the problem of quadratically tightly approximating the randomized query complexity of Boolean functions R(f). The certificate complexity C(f) is such a complexity measure for the zero-error randomized query complexity R0(f): C(f) ≤R0(f) ≤C(f)2. In the first part of the paper we introduce a new complexity measure, expectational certificate complexity EC(f), which is also a quadratically tight bound on R0(f): EC(f) ≤R0(f) = O(EC(f)2). For R(f), we prove that EC2/3 ≤R(f). We then prove that EC(f) ≤C(f) ≤EC(f)2 and show that there is a quadratic separation between the two, thus EC(f) gives a tighter upper bound for R0(f). The measure is also related to the fractional…
Variances as order parameter and complexity measure for random Boolean networks
2005
Several order parameters have been considered to predict and characterize the transition between ordered and disordered phases in random Boolean networks, such as the Hamming distance between replicas or the stable core, which have been successfully used. In this work, we propose a natural and clear new order parameter: the temporal variance. We compute its value analytically and compare it with the results of numerical experiments. Finally, we propose a complexity measure based on the compromise between temporal and spatial variances. This new order parameter and its related complexity measure can be easily applied to other complex systems.
Minimal forbidden words and symbolic dynamics
1996
We introduce a new complexity measure of a factorial formal language L: the growth rate of the set of minimal forbidden words. We prove some combinatorial properties of minimal forbidden words. As main result we prove that the growth rate of the set of minimal forbidden words for L is a topological invariant of the dynamical system defined by L.